package leetcode.code1206;

public class Skiplist {

	Node root;

	public Skiplist() {
		root = new Node(0);
	}

	// 0层最接近num的位置
	private Node close2num(int num) {
		Node cur = root;
		while (cur.level > 0) { // 从上层跳下层
			while (cur.right != null && cur.right.val < num) {// 从左往右跳
				cur = cur.right;
			}
			cur = cur.down;
		}
		// 最后一层，最接近num的位置
		while (cur.right != null && cur.right.val < num) {// 从左往右跳
			cur = cur.right;
		}
		return cur;
	}

	public boolean search(int target) {
		Node node = this.close2num(target);
		// 下一个数就是target，search成功
		return node.right != null && node.right.val == target;
	}

	public void add(int num) {
		Node node = this.close2num(num);
		if (node.right != null && node.right.val == num) {
			// 存在num，num数量增加1
			node.right.size += 1;
		} else {
			int numLevel = this.myLevel();// num的level
			// 抬高root
			for (int i = root.level + 1; i <= numLevel; i++) {
				Node newNode = new Node(i);
				newNode.down = root;
				root = newNode;
			}
			Node cur = root;
			// numLevel之上，尽量往右贴近num
			while (cur.level > numLevel) {
				while (cur.right != null && cur.right.val < num) {// 从左往右跳
					cur = cur.right;
				}
				cur = cur.down;
			}
			// 从cur的level开始直至0层，添加num到已有网络中
			add(cur, num, null);
		}
	}

	private void add(Node cur, int num, Node up) {
		if (cur == null) {
			return;
		}
		Node newNode = new Node(cur.level, num);
		while (cur.right != null && cur.right.val < num) {// 从左往右跳
			cur = cur.right;
		}
		newNode.right = cur.right;
		cur.right = newNode;
		if (up != null) {
			up.down = newNode;
		}
		// 编下一级，newNode是下一级的上级
		this.add(cur.down, num, newNode);
	}

	public boolean erase(int num) {
		Node target = this.close2num(num);
		if (target.right == null || target.right.val != num) {
			return false;
		}
		if (--target.right.size == 0) {
			Node cur = root;
			while (cur != null && cur.level >= 0) {
				while (cur.right != null && cur.right.val < num) {// 从左往右跳
					cur = cur.right;
				}
				if (cur.right != null && cur.right.val == num) {
					cur.right = cur.right.right;
				}
				cur = cur.down;
			}
		}
		return true;
	}

	private int myLevel() {
		int ans = 0;
		while (Math.random() < 0.5) {
			ans++;
		}
		return ans;
	}

	class Node {
		int level;// 当前节点的level
		int size;// 这个数出现的次数
		int val;// 这个数值
		Node right;// 这个节点的右侧
		Node down;// 这个节点的下方

		public Node(int _level) {
			level = _level;
			val = -1;
			size = 0;
		}

		public Node(int _level, int _val) {
			level = _level;
			val = _val;
			size = 1;
		}
	}

	public void print() {
		if (root == null) {
			return;
		}
		Node node = root;
		Node cur = root;
		while (cur != null) {
			while (node != null) {
				System.out.print("," + node.val);
				node = node.right;
			}
			System.out.println("");
			cur = cur.down;
			node = cur;
		}
	}

	public static void main(String[] args) {

		test1();
	}

	public static void test1() {

		Skiplist sl = new Skiplist();
		sl.add(7);
		sl.add(8);
		sl.add(9);
		sl.add(12);
		sl.add(7);
		sl.add(4);
		sl.add(5);
		System.out.println(sl.search(12));
		System.out.println(sl.search(13));
		System.out.println(sl.search(2));
		System.out.println(sl.search(5));
		System.out.println(sl.search(0));
		System.out.println(sl.search(13));
		System.out.println(sl.search(0));
		sl.print();

	}

	public static void test() {

		Skiplist skiplist = new Skiplist();
		skiplist.add(1);
//		System.out.println(skiplist.search(2));
		skiplist.add(2);
//		System.out.println(skiplist.search(2));
		System.out.println(skiplist.search(3));
		skiplist.add(3);
		System.out.println(skiplist.search(3));
		skiplist.add(3);
		System.out.println(skiplist.search(3));
		skiplist.erase(3);
		System.out.println(skiplist.search(3));
		skiplist.erase(3);
		System.out.println(skiplist.search(3));
//		System.out.println(skiplist.search(4));
		skiplist.add(4);
//		System.out.println(skiplist.search(4));
		skiplist.erase(4);
//		System.out.println(skiplist.search(4));
		skiplist.add(5);
//		System.out.println(skiplist.search(100));
//		System.out.println(skiplist.search(5));
		System.out.println("");

	}

}
